1. Field of the Invention
This invention relates to computer systems, specifically to computer-aided image processing, and more specifically to the merging of images to form a composite image.
2. Description of the Related Art
Image capture devices, such as cameras, may be used to capture an image of a section of a view or scene, such as a section of the front of a house. The section of the view or scene whose image is captured by a camera is known as the field of view of the camera. Adjusting a lens associated with a camera may increase the field of view. However, there is a limit beyond which the field of view of the camera cannot be increased without compromising the quality, or “resolution”, of the captured image. Further, some scenes or views may be too large to capture as one image with a given camera at any setting. Thus, it is sometimes necessary to capture an image of a view that is larger than can be captured within the field of view of a camera. In these instances, multiple overlapping images of segments of the view or scene may be taken, and then these component images may be joined together, or merged, to form a composite image.
One type of composite image is known as a panoramic image. A panoramic image may have a rightmost and leftmost image that each overlap only one other image, or alternatively the images may complete 360°, where all images overlap at least two other images. In the simplest type of panoramic image, there is one row of images, with each image at most overlapping two other images. However, more complex composite images may be captured that have two or more rows of images; in these composite images, each image may potentially overlap more than two other images. For example, a motorized camera may be configured to scan a scene according to an M×N grid, capturing an image at each position in the grid. Other geometries of composite images may be captured.
Computer programs and algorithms exist for assembling a single composite image from multiple potentially overlapping component images. The general paradigm for automatic image stitching techniques is to first detect features in individual images; second, to establish feature correspondences between pairs of images; and third, to use the feature correspondences to infer the geometric relationship among the images. To establish accurate feature correspondences for all of the component images, feature matching is typically performed for all possible pairs of images in the set of component images. Therefore, the total number of pairs of image for which feature matching is performed may be quadratic in terms of the number of images. Thus, for a large number of component images, the second step (feature matching) may be very time-consuming.